package com.leetcode.tree.bst;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/7/10 23:00
 */
public class ConvertBST_538 {

    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        getSum(root);
        traverse(root);
        return root;
    }

    // 从左至右
    private void getSum(TreeNode root) {
        if (root == null) return;
        getSum(root.left);
        sum += root.val;
        getSum(root.right);
    }

    private void traverse(TreeNode root) {
        if (root == null) return;
        traverse(root.left);
        sum -= root.val;
        root.val += sum;
        traverse(root.right);
    }

    // 更优解
    private void traverse2(TreeNode root) {
        if (root == null) return;
        traverse2(root.right);
        root.val += sum;
        sum += root.val;
        traverse2(root.left);
    }
}
